package kyssion.leetcode.num51_100;

public class code72_编辑距离 {
    public static void main(String[] args) {
        System.out.println(new code72_编辑距离().minDistance(
                "zoologicoarchaeologist",
                "zoogeologist"
        ));
        System.out.println(new code72_编辑距离().minDistance(
                "sea", "eat"
        ));
        System.out.println(new code72_编辑距离().minDistance(
                "horse", "ros"
        ));
        System.out.println(new code72_编辑距离().minDistance(
                "intention", "execution"
        ));
    }

    /**
     * 一个标准的困难级别的dp问题.... 感觉真的会了不难
     * 其实是使用递归的思想去解决dp问题
     * 首先看见题目中有三种变量类型 删除,添加,修改
     * 这里其实想到了一个推论如果我想知道了 word2 的 第x字母在 word1 的第y个位置的最小修改数量
     * 我们只要遍历这三种情况就可以等到结论了, 1. 修改他,dp[x-1][y-1]+x==y?0:1
     *                                   2. 删除他 dp[x-1][y]+1 (x-1 匹配到y 删除 一个)
     *                                   3. 添加态 dp[x][y-1]+1 (我的x位置匹配到y-1 然后再增加一个y)
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        if (word1.length() == 0) {
            return word2.length();
        }
        if (word2.length() == 0) {
            return word1.length();
        }
        int[][] dp = new int[word1.length()][word2.length()];
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        for (int a = 0; a < word2.length(); a++) {
            if (chars1[0] == chars2[a]) {
                dp[0][a] = a;
            } else {
                if (a == 0) {
                    dp[0][a] = a + 1;
                } else {
                    dp[0][a] = Math.min(dp[0][a - 1] + 1, a + 1);
                }
            }
        }
        for (int a = 1; a < word1.length(); a++) {
            for (int b = 0; b < word2.length(); b++) {
                int same = chars1[a] == chars2[b] ? 0 : 1;
                if (b == 0) {
                    dp[a][b] = Math.min(1 + dp[a - 1][b], same + a);
                } else {
                    dp[a][b] = Math.min(Math.min(1 + dp[a - 1][b], 1 + dp[a][b - 1]), dp[a - 1][b - 1] + same);
                }
            }
        }
        return dp[word1.length() - 1][word2.length() - 1];
    }
}
